/*
 * @lc app=leetcode.cn id=74 lang=swift
 *
 * [74] 搜索二维矩阵
 采用二分搜索即可
 竖采用二分
 横也采用二分
 log m * n
 */

// @lc code=start
class Solution74 {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        let rowCount = matrix.count
        let colCount = matrix[0].count
        var left = 0
        var right = rowCount * colCount - 1
        while left <= right {
            let mid = (left + right) / 2
            let midRow = mid / colCount
            let midCol = mid % colCount
            if matrix[midRow][midCol] < target {
                left = mid + 1
            } else if matrix[midRow][midCol] == target {
                return true
            } else {
                right = mid - 1
            }
        }
        return false
    }
    static func test() {
        let array = [[1,3,5]]
        let target = 1
        let result = Solution74().searchMatrix(array, target)
        print(result)
    }
}
// @lc code=end

